Predicting the direction of conditional branches is one of the key bottlenecks limiting processor performance. Various techniques have been proposed and implemented to perform such predictions. Some processors implement a sequence of dynamic prediction stages, each improving on the previous stage, and each using a different type of predictor. A tag-hit generated from an array access using a branch address is used to determine whether the prediction from the current stage should replace the prediction coming from the previous stage. These dynamic predictions use branch history (local or global), path information, or other information generated during execution of a program. Accordingly, as execution continues dynamic predictions can become more refined and thus improve over time.
The end result generated by a predictor is a prediction of the direction of the conditional branch. Based on this prediction, a processor can begin execution of the path predicted by the predictor. In this way, improved performance may be realized, as predictive or speculative execution may occur and then may be committed if the prediction proves to be correct. One of the key limits to a predictor is that it must be kept small, so that the predictor can be able to generate new predictions rapidly to keep up with a processor pipeline. Unfortunately, this small size prevents the predictor from holding all of the branch targets or branch patterns it may see. Furthermore, the small size may cause frequent disruptions or evictions of data present in the predictor. These disruptions can be both time consuming and prevent maintenance of prediction information that may prove valuable during program execution.
For conditional branches that do not have historical information present in a dynamic predictor, static prediction information may be available to provide a static prediction. Such static predictions are based not on actual program operation, but instead on predetermined characteristics with respect to a given branch, which could include branch direction, opcode, displacement length, or any other piece or combination of information available at compile time. While these static predictions are generally accurate, they can cause mispredictions, owing to their static nature.